from typing import List


class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        minus_num = 0
        have_zero = False
        total_sum = 0
        min_abs = 100001
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                if matrix[i][j] < 0:
                    minus_num += 1
                elif matrix[i][j] == 0:
                    have_zero = 0
                total_sum += abs(matrix[i][j])
                min_abs = min(min_abs, abs(matrix[i][j]))

        if have_zero or minus_num % 2 == 0:
            return total_sum
        else:
            return total_sum - min_abs * 2


if __name__ == "__main__":
    print(Solution().maxMatrixSum(matrix=[[1, -1], [-1, 1]]))  # 4
    print(Solution().maxMatrixSum(matrix=[[1, 2, 3], [-1, -2, -3], [1, 2, 3]]))  # 16
